package code;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class Palindromic {
	
	public String longestPalindrome(String s){
		int len=s.length();
		StringBuilder sb=new StringBuilder();
		int i;
		for(i=0;i<len;i++){
			sb.append("#");
			sb.append(s.charAt(i));
		}
		sb.append("#");
		int index,mx;
		int n=len*2+1;
		int[] p=new int[n];
		mx=0;
		index=0;
		int max=0;
		int idx=0;
		for(i=1;i<n;i++){
			if(mx>i)
				p[i]=p[2*index-i]>mx-i?mx-i:p[2*index-i];
			else 
				p[i]=1;
			for(;i-p[i]>=0 && i+p[i]<n && sb.charAt(i-p[i])==sb.charAt(i+p[i]);p[i]++)
				;
			if(i+p[i]>mx){
				mx=i+p[i];
				index=i;
			}
			if(max<p[i]){
				max=p[i];
				idx=i;
			}
		}
		String res=(String) sb.subSequence(idx-p[idx]+1,idx+p[idx]);
		res=res.replaceAll("#", "");
		return res;
	}
	
	public static class Interval{
		int start;
		int end;
		Interval(){
			start=0;
			end=0;
		}
		Interval(int s,int e){
			start=s;
			end=e;
		}
	}
	public static class IntervalComparator implements Comparator<Interval>{

		@Override
		public int compare(Interval o1, Interval o2) {
			// TODO Auto-generated method stub
			if(o1.start==o2.start)
				return o1.end-o2.end;
			return o1.start-o2.start;
		}
	}
	
	public List<Interval> merge(List<Interval> intervals) {
        List<Interval> list=new ArrayList<Interval>(intervals);
        Collections.sort(list, new IntervalComparator());
        int n=list.size();
        intervals.clear();
        int i,j;
        for(i=0;i<intervals.size();i++){
        	System.out.println(list.get(i).start+"  "+list.get(i).end);
        }
        for(i=0;i<n;){
        	int max=list.get(i).end;
        	for(j=i+1;j<n;j++){
        		if(list.get(j-1).end>max) 
        			max=list.get(j-1).end;
        		if(max<list.get(j).start)
        			break;
        	}
        	j--;
        	if(j==n-1 && max<list.get(j).end)	max=list.get(j).end;	
        	if(list.get(i).end<max)
        		list.get(i).end=max;
        	intervals.add(list.get(i));
        	i=j+1;
        }
        for(i=0;i<intervals.size();i++){
        	System.out.println(intervals.get(i).start+"  "+intervals.get(i).end);
        }
		return intervals;
    }
	public static void main(String[] args){
		String s="aab";
		Palindromic palin=new Palindromic();
//		System.out.println(palin.longestPalindrome(s));
		Interval a=new Interval(2,3);
		Interval b=new Interval(4,5);
		Interval c=new Interval(6,7);
		Interval d=new Interval(8,9);
		Interval e=new Interval(1,10);
		List<Interval> intervals=new ArrayList<Interval>();
		intervals.add(d);
		intervals.add(a);
		intervals.add(c);
		intervals.add(b);
		intervals.add(e);
		palin.merge(intervals);
	}
}
